// 给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
#include<bits/stdc++.h>
using namespace std;
struct TreeNode
{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x):val(x),left(nullptr),right(nullptr){};
};

class Solution
{
private:
    /* data */
public:
    vector<int> preorderTraversal(TreeNode* root){
        vector<int> res;
        if(root==nullptr){
            return res;
        }
        stack<TreeNode*> sta;
        while(!sta.empty() || root!=nullptr){
            while(root!=nullptr){
                res.emplace_back(root->val);
                sta.push(root);
                root=root->left;
            }
            root = sta.top();
            sta.pop();
            root=root->right;
        }
        return res;
    }
};

int main(int argc, char const *argv[])
{
    TreeNode* root = new TreeNode(1);
    root->right=new TreeNode(2);
    root->right->left=new TreeNode(3);
    vector<int> res;
    Solution s;
    res = s.preorderTraversal(root);
    for(auto i:res){
        cout<<i<<endl;
    }
    return 0;
}


